package me.mingshan.leetcode;

/**
 * https://leetcode-cn.com/problems/container-with-most-water/
 *
 * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 *
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 返回容器可以储存的最大水量。
 *
 * 说明：你不能倾斜容器。
 *
 * 示例 1：
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * 示例 2：
 *
 * 输入：height = [1,1]
 * 输出：1
 *
 * @author mingshan
 */
public class L_11_MaxArea {
  public static void main(String[] args) {
    int[] arr = {1,8,6,2,5,4,8,3,7};
    System.out.println(maxArea2(arr)); // 49
  }

  /**
   * 暴力解法
   *
   * @param height
   * @return
   */
  public static int maxArea(int[] height) {
    if (height == null || height.length == 0) {
      return 0;
    }

    int result = 0;

    for (int i = 0; i < height.length; i++) {
      for (int j = i + 1; j < height.length; j++) {
        int area = Math.min(height[i], height[j]) * Math.abs(i - j);
        if (area > result) {
          result = area;
        }
      }
    }

    return result;
  }

  /**
   * 双指针算法
   * <p>
   * 思路：
   * 一个容器能盛多少水，取决于最矮的那个
   *
   * @param height
   * @return
   */
  public static int maxArea2(int[] height) {
    if (height == null || height.length == 0) {
      return 0;
    }

    int result = 0;
    int left = 0;
    int right = height.length - 1;

    while (left < right) {
      // 计算体积： 最小的高度 * 宽度
      int area = Math.min(height[left], height[right]) * Math.abs(left - right);
      if (area > result) {
        result = area;
      }

      // 谁矮移动谁
      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }

    return result;
  }
}
